CF1268B Domino for Young

一道画图猜性质题

题解：

首先，十分贪心的，偶数高度列可以自己消完自己，奇数高度列则会剩下最底下一个

手动画图可以很快发现这么一个性质：若两个奇数高度列之间有连续的偶数个偶数高度列，那么这两个奇数高度列的最底下也会被消掉，也就是说，可以多放一个骨牌

于是我们就可以开一个栈，记录奇数高度列出现的位置，如果栈顶与当前的距离为偶数就可弹掉，答案加一

又因为下标奇偶性加上一个偶数不会改变，所以栈里只要存下标是奇还是偶就行了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

int n;
long long ans;
stack<int> s;

signed main(){
    read(n);
    for(int i=1,x;i<=n;i++){
        read(x);
        ans+=x>>1;
        if(x&1){
            if(!s.empty()&&(s.top()^i&1)){
                s.pop();
                ans++;
            }
            else s.push(i&1);
        }    
    }
    write(ans);
}